package com.congee02;

import java.util.*;

public class FindCircleNum_Cast {

    public int findCircleNum(int[][] isConnected) {

        int n = isConnected.length;

        List<Integer>[] graph = new List[n];

        for (int from = 0 ; from < n ; from ++ ) {
            for (int to = 0 ; to < n ; to ++ ) {

                // 自环，无意义
                if (from == to) {
                    continue;
                }

                // 无通路
                if (isConnected[from][to] == 0) {
                    continue;
                }

                if (graph[from] == null) {
                    graph[from] = new ArrayList<>();
                }

                graph[from].add(to);

            }
        }

        boolean[] visited = new boolean[n];
        int ans = 0;
        for (int i = 0 ; i < n ; i ++ ) {

            if (! visited[i]) {
                ans ++;
                dfsHelp(graph, visited, i);
            }

        }

        return ans;
    }

    private void dfsHelp(List<Integer>[] graph, boolean[] visited, int cur) {

        visited[cur] = true;

        if (graph[cur] == null) {
            return;
        }

        for (Integer neighbor : graph[cur]) {
            if (! visited[neighbor]) {
                dfsHelp(graph, visited, neighbor);
            }
        }

    }

}
